package main.leetcode.clockin.April;

/**
 * 面试题08.11.硬币
 *
 * <p>硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
 *
 * <p>示例1: 输入: n = 5 输出：2 解释: 有两种方式可以凑成总金额: 5=5 5=1+1+1+1+1
 *
 * <p>示例2: 输入: n = 10 输出：4 解释: 有四种方式可以凑成总金额: 10=10 10=5+5 10=5+1+1+1+1+1 10=1+1+1+1+1+1+1+1+1+1 说明：
 *
 * <p>注意: 你可以假设： 0 <= n (总金额) <= 1000000
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/coin-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day23 {
    public static void main(String[] args) {
        System.out.println(new day23().waysToChange(30));
    }

    public int waysToChange(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        int mod = 1000000007;
        int[] coins = new int[] {25, 10, 5, 1};
        for (int i = 0; i < 4; ++i) {
            int coin = coins[i];
            for (int j = coin; j <= n; ++j) {
                dp[j] = (dp[j] + dp[j - coin]) % mod;
            }
        }
        return dp[n];
    }
}
